package mazeBug.info.gridworld.maze;

import info.gridworld.actor.Actor;
import info.gridworld.actor.Bug;
import info.gridworld.actor.Flower;
import info.gridworld.actor.Rock;
import info.gridworld.grid.*;

import java.awt.Color;
import java.util.ArrayList;
import java.util.Stack;

import javax.swing.JOptionPane;

/**
 * A <code>MazeBug</code> can find its way in a maze. <br />
 * The implementation of this class is testable on the AP CS A and AB exams.
 */
public class MazeBug extends Bug {
    public Location next; // 记录Bug下一个将要去的位置
    public Location last; // 记录Bug上一时刻所在的位置
    public boolean isEnd = false; // 判断是否到达终点
    // 记录Bug到达终点的最短路径（不包括返回路径）
    public Stack<ArrayList<Location>> crossLocation = new Stack<ArrayList<Location>>();
    public Integer stepCount = 0; // 记录Bug走过的步数
    boolean hasShown = false; // final message has been shown
    public Stack<Location> rec = new Stack<Location>(); // 记录过程
    public int[] freq = { 1, 1, 1, 1 }; // 默认每个方向次数为1

    /**
     * Constructs a box bug that traces a square of a given side length
     *
     */
    // 初始化
    public MazeBug() {
        setColor(Color.GREEN);
        last = new Location(0, 0);
    }

    /**
     * Moves to the next location of the square.
     */
    public void act() {
        if (stepCount == 0) {
            Location loc = this.getLocation();
            rec.push(loc);
        }
        boolean willMove = canMove(); // 判断当前Bug能否行动
        if (isEnd == true) {
            // to show step count when reach the goal
            if (hasShown == false) { // 打印结果
                String msg = stepCount.toString() + " steps";
                JOptionPane.showMessageDialog(null, msg);
                hasShown = true;
            }
        } else if (willMove) { // 未到达终点，则继续探索
            move();
            // increase step count when move
            stepCount++;
        } else // 如果不能走
        {
            goBack(); // 回溯
            stepCount++;
        }
    }

    /**
     * 回溯算法。进入此算法说明当前的路径已经全部探索完了，此时不再考虑路径是否valid（路径是否被探
     * 索过），而是需要根据存在栈里Bug的过去探索路径，将Bug回溯到前一个valid的状态，即回溯到前一个
     * 有新路径可以探索的位置，继续进行探索。（栈不可能为空，如果为空说明所有路径都探索完了）
     */
    public void goBack() {
        Grid<Actor> grid = getGrid();
        if (grid == null) {
            return;
        }
        Location myLoc = this.getLocation();
        rec.pop(); // 出栈
        last = rec.peek(); // 拿到Bug上一时刻所在的位置
        setDirection(getLocation().getDirectionToward(last)); // 将Bug移动到上一时刻所在位置
        moveTo(last);
        int direction = last.getDirectionToward(myLoc);
        // the last direction decrease 1
        freq[direction / 90]--;
        Flower flower = new Flower(getColor()); // 将花朵放置在Bug刚刚所在的位置
        flower.putSelfInGrid(grid, myLoc); // 这样就使得Bug回到了前一个位置，并用花标记了走过的路径，使得Bug不会回头
    }

    /**
     * Find all positions that can be move to.
     *
     * @param loc
     *            the location to detect.
     * @return List of positions.
     */
    /**
     * 在本题中，为了实现深度优先，我们用花朵来对Bug走过的路径进行占位，使得Bug在有新路径未探索、
     * 不需要回溯的状态下，不会回到曾经走过的路径中去。所以在考虑可行路径时，不需要担心Bug回到之前
     * 的位置的状况出现，因为我们已经用花朵对过去路径占位了。
     */
    // 寻找东西南北四个路径中的可行路径
    public ArrayList<Location> getValid(Location loc) {
        int dir[] = { Location.NORTH, Location.EAST, Location.SOUTH, Location.WEST };

        Grid<Actor> grid = getGrid();
        if (grid == null) {
            return null;
        }
        ArrayList<Location> valid = new ArrayList<Location>();
        Location adjacentLocation;
        Actor adjacentActor;
        // 遍历四个方向，获得可行的路线
        // Determine the valid loc in the four directions
        for (int i = 0; i < 4; i++) {
            adjacentLocation = loc.getAdjacentLocation(dir[i]);
            if (grid.isValid(adjacentLocation)) {
                adjacentActor = grid.get(adjacentLocation);
                // the condition of Exit
                if (adjacentActor instanceof Rock && adjacentActor.getColor().equals(Color.RED)) {
                    next = adjacentLocation;
                    ArrayList<Location> Exit = new ArrayList<Location>();
                    Exit.add(next);
                    return Exit;
                } else if (adjacentActor == null) {
                    valid.add(adjacentLocation);
                }
            }
        }
        return valid;
    }

    /**
     * Tests whether this bug can move forward into a location that is empty or
     * contains a flower.
     *
     * @return true if this bug can move.
     */
    // 如果可移动的位置不是0个，就说明可移动
    public boolean canMove() {
        ArrayList<Location> valid = new ArrayList<Location>();
        valid = getValid(this.getLocation());
        if (valid.size() > 0) {
            return true;
        }
        return false;
    }

    /**
     * Moves the bug forward, putting a flower into the location it previously
     * occupied.
     */
    // 来到这个函数，说明有未探索的路径，不需要回溯
    public void move() {
        Grid<Actor> gr = getGrid();
        if (gr == null)
            return;
        Location loc = getLocation();// 当前所在位置
        ArrayList<Location> valid = new ArrayList<Location>(); // 获取可行位置
        valid = getValid(loc);
        if (valid.size() == 1) { // 如果可行的位置只有一个，直接过去即可
            next = valid.get(0);
            int direction = loc.getDirectionToward(next);
            freq[direction / 90]++;
        } else if (valid.size() == 0) {
            System.out.println("valid.size==0\n");
            goBack();
            stepCount++;
        } else { // 如果可行的位置大于一个，则按照方向的概率估计选择一个
            boolean flag[] = { false, false, false, false };// 看某个方向有没有出现
            for (Location l : valid) {
                int direction = loc.getDirectionToward(l);
                flag[direction / 90] = true;
            }
            int sum_valid = 0;
            for (int i = 0; i < 4; i++) {
                sum_valid += freq[i];
            }
            int choice = -1;
            do {
                double random = (double) (Math.random() * sum_valid);
                if (random <= freq[0] && flag[0] == true)
                    choice = 0;
                else if (random > freq[0] && random <= (freq[0] + freq[1]) && flag[1] == true)
                    choice = 1;
                else if (random > freq[0] + freq[1] && random <= (freq[0] + freq[1] + freq[2]) && flag[2] == true)
                    choice = 2;
                else if (random > (freq[0] + freq[1] + freq[2]) && flag[3] == true)
                    choice = 3;
            } while (choice == -1);
            System.out.println("choice=" + choice);

            for (Location l : valid) {
                int direction = loc.getDirectionToward(l);
                if ((int) (direction / 90) == choice) {
                    System.out.println("direction==choice\n");
                    next = l;
                    freq[direction / 90]++;
                    break;
                }
            }
        }
        if (gr.isValid(next)) {
            Actor actor = (Actor) gr.get(next);
            if (actor instanceof Rock && actor.getColor().equals(Color.RED)) {
                isEnd = true;
            }
            setDirection(getLocation().getDirectionToward(next));
            moveTo(next); // 移到下一个位置
            rec.push(next); // 入栈，记录所经过的地方
        } else {
            System.out.println("removeSelfFromGrid()");
            removeSelfFromGrid();
            // goBack();
            // stepCount++;
        }
        Flower flower = new Flower(getColor()); // 用花标记曾经走过的路径，防止再走一次
        flower.putSelfInGrid(gr, loc);
    }

}
